原网址：https://www.chenyajun.com/2010/06/23/5078
前面几节谈到的游戏可以用图理论来描述，考虑一个图 G = (X, F)；其中 X 是顶点，也是先前游戏中可能的态势。F 是一个函数，对于 X 中的任意一个 x，F(x) 的值都出现在 X 中，对于 X 的一个元素 x，F(x) 的含义是一个玩家从 x 出发可以移动到的局势。
对于一个两人的类似前面的游戏而言，可以在一个如此这样的图上进行博弈，首先指定一个起始点 x0，并使用下面的规则：
（1）玩家 I 从 x0 开始首先移动；
（2）玩家交替移动；
（3）在 x 态势时，玩家要将态势转移到另一个态势 y，其中 y 是 F(x) 中的元素。
为简单起见，假定图中不存在环，元素个数为 n，其中最长的一条路径也不超过 n。那么对于前面我们分析的减法游戏，其中 S = {1, 2, 3}。假定游戏中指定对 n 进行减法操作。X = {0, 1, 2…, n} 是图顶点。F(0) 是空集。F(1) = {0}，F(2) = {0, 1}。 对于 2<= k <= n，F(k) = {k -3, k -2, k -1}。
因此这个游戏的图大致如下。其中 n = 10。
“3-1”)边的方向代表了可能的移动。
SG 函数
这种图可以通过分析 SG 函数来分析。
所谓图 (X, F) 的 SG 函数 g 是定义在 X 上的一个函数。
g(x) = min{n ≥ 0 : n ≠ g(y) for y ∈ F(x)}。换句话说，g(x) ：是一个非负整数；尽可能的小；不出现在 x 的后缀节点的 g 函数取值中。
这是一个递归定义。但可以通过倒推来取得节点的值。对于终点 x，g(x) = 0，因为 F(x) 是空集。
如果一个态势的 g(x) = 0 那么它就是 P 态，否则就是 N 态。
下面的图描述了 g 函数的求解过程，在开始所有的顶点本是没有数字的。在开始，所有的终点 SG 函数值为 0，一共有 4 个终点，它们位于图的左边和下边。对于点 a，它的后缀 SG 函数为 0，那么它自身的 SG 值就是 1，它是所有没有出现在 a 后缀节点的 SG 值的最小值。那么 b 的 SG 值就是 2，因为它有 2 个后缀，一个是 a，令一个是终点，它们的 SG 值分别是 1 和 0，那么它的 SG 值就是 2。那么 c 的 SG 值就是 0，因为 c 只有一个后缀 a，而 a 的 SG 值为 1，那么没有出现在 c 后缀节点的 SG 值的最小值就是 0。
对于 S = {1, 2, 3} 的减法游戏其 SG 函数是多少？
终点 0， SG 值为 0, 1 只能移到 0，而 g(0) = 0，所以 g(1) = 1，同样，2 可以移动到 0 和 1，而 g(0) = 0，g(1) = 1，故 g(2) = 2，3 可以移动到 0，1，2 ，它们各自的 g(0) = 0, g(1) = 1, g(2) = 2，因此 g(3) = 3，但是对于 4 只能移动到 1，2，3，其各自的 SG 值为 1,2,3，故 g(4) = 0。
容易发现 g(x) = x( mod 4)。
考虑一种移石子游戏：每次必须移走至少剩余的一半，我们可以如下计算 SG 函数：
x 0 1 2 3 4 5 6 7 8 9 10 11 12 . . . g(x) 0 1 2 2 3 3 3 3 4 4 4 4 4 . . .
g(x) = min{k: power(2,k) > x}。